#include <stdio.h>
#include <stdlib.h>

/** 
 * 本身0
 * 未连接MAX
 */
#define MAX 32767

typedef struct Graph{
    char *vexs;
    int **arcs;
    int vexNum;
    int arcNum;
} Graph;
/**
 * 这个表的意思是 第一个点到每一个点的距离
 * 0 1 2 3 4 5 对应所有点
 * 1 1 1 1 1 1 起点 第一次只有一个顶点 当选出后 weight=0 然后二层循环找到到每一个索引的顶点最短的点 更新这一层
 * 0 6 1 5 0 0 从这里选最短的
*/

//数组的每一个元素都是结构体 他的索引代表顶点
typedef struct Edge { //记录集合U中最小权值边的定点信息
    char vex;  
    int weight;//表示到对应索引的最小值 0代表加入U集合  
} Edge;

Edge *initEdge(Graph *G, int index) //index表示起始顶点
{
    Edge *edge = (Edge *)malloc(sizeof(Edge) * G->vexNum);
    for (int i = 0; i < G->vexNum; i++) {
        edge[i].vex = G->vexs[index];
        edge[i].weight = G->arcs[index][i];
    }
    return edge;
}

int getMinIndex(Edge *edge , Graph *G)
{
    int index;
    int min = MAX;
    for (int i = 0; i < G->vexNum; i++) {
        if (edge[i].weight != 0 && edge[i].weight < min) {
            min = edge[i].weight;
            index = i;
        }
    }
    return index;
}

void prim(Graph *G, int index) 
{
    int min;
    Edge *edge = initEdge(G, index);
    for (int i = 0; i < G->vexNum-1; i++) {//最小生成n-1条边
        min = getMinIndex(edge, G);
        printf("v%c --> v%c, weight=%d\n", edge[min].vex, G->vexs[min], edge[min].weight);
        edge[min].weight = 0;//加入U  当weight=0时代表顶点加入集合U中 
        //此时加入一次就更新一次最小边的权值也就是下面这个for循环
        for (int j = 0; j < G->vexNum; j++) {
            if (G->arcs[min][j] < edge[j].weight) {
                edge[j].weight = G->arcs[min][j];//权值
                edge[j].vex = G->vexs[min];//更新起点
            }
        }
    }
}

Graph *initGraph(int vexNum) //顶点数
{
    Graph *G = (Graph *)malloc(sizeof(Graph));
    G->arcs = (int **)malloc(sizeof(int *) * vexNum);
    G->vexs = (char *)malloc(sizeof(char) * vexNum);
    for (int i = 0; i < vexNum; i++) {
        G->arcs[i] = (int *)malloc(sizeof(int) * vexNum);
    }
    G->arcNum = 0;
    G->vexNum = vexNum;
    return G;
}

void createGraph(Graph *G, char *vexs, int *arcs)
{
    for (int i = 0; i < G->vexNum; i++) {
        G->vexs[i] = vexs[i];//赋值边
        for (int j = 0; j < G->vexNum; j++) { //注意此时只是普通的二级指针
            G->arcs[i][j] = *(arcs + i * G->vexNum + j);
            if (G->arcs[i][j] != 0 && G->arcs[i][j] != MAX) {
                G->arcNum++;
            }
        }
    }
    G->arcNum /= 2;
}

void DFS(Graph *G, int *visited, int index) //索引第一个节点开始
{
    printf("%c ", G->vexs[index]);//访问
    visited[index] = 1;
    for (int i = 0; i < G->vexNum; i++) {
        if (G->arcs[index][i] > 0 && G->arcs[index][i] != MAX && !visited[i]) {//遍历 + 递归
            DFS(G, visited, i);                                                //连通条件判断
        }
    }
}

int main(void)
{
    Graph* G = initGraph(6);
    int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
    for (int i = 0; i < G -> vexNum; i++)
        visited[i] = 0;
    int arcs[6][6] = {
            0, 6, 1, 5, MAX, MAX,
            6, 0, 5, MAX, 3, MAX,
            1, 5, 0, 5, 6, 4,
            5, MAX, 5, 0, MAX, 2,
            MAX, 3, 6, MAX, 0, 6,
            MAX, MAX, 4, 2, 6, 0
    };
    createGraph(G, "123456", (int*)arcs);
    DFS(G, visited, 0);
    printf("\n");
    prim(G, 0);
    return 0;
    //DFS(G, visited, 0);
    return 0;
}